package m202405.d28;

import java.util.Arrays;
import java.util.Stack;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/28 17:09
 */
public class Q84 {

    public static void main(String[] args) {
        Q84 q84 = new Q84();
        q84.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3});
    }

    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        Arrays.fill(left, -1);
        Stack<int[]> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && stack.peek()[1] >= heights[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek()[0];
            stack.push(new int[]{i, heights[i]});
        }
        int[] right = new int[heights.length];
        Arrays.fill(right, -1);
        stack.clear();
        for (int i = heights.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek()[1] >= heights[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? heights.length : stack.peek()[0];
            stack.push(new int[]{i, heights[i]});
        }

        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            max = Math.max(heights[i] * (right[i] - left[i]-1), max);
        }
        return max;
    }
}
